Weighings and Puzzles
My co-author Konstantin Knop wrote a charming book, Weighings and Algorithms: from Puzzles to Problems. The book contains more than one hundred problems. Here are a couple of my favorites that I translated for you:
There is one gold medal, three silver medals and five bronze medals. It is known that one of the medals is fake and weighs less than the corresponding genuine one. Real medals made of the same metal weigh the same and from different metals do not. How can you use a balance scale to find the fake medal in two weighings?
There are 15 coins, out of which not more than seven are fake. All genuine coins weigh the same. Fake coins might not weigh the same, but they differ in weight from genuine coins. Can you find one genuine coin using a balance scale 14 times? Can you do it using fewer weighings?
You might get the impression that the latter problem depends on two parameters. Think about it: It is necessary that the majority of the coins are genuine in order to be able to solve the problem. In fact, the number of weighings depends on just one parameter: the total number of coins. Denote a(n) the optimal number of weighings needed to find a genuine coin out of n coins, where more than half of the coins are genuine. Can you calculate this sequence?
Hint. I can prove that a(n) ≤ A011371(n-1); that is, the optimal number of weighings doesn’t exceed n − 1 − (number of ones in the binary expansion of n−1).
Share:
Anonymous Rex:
Alonso, Laurent; Reingold, Edward M.; and Schott, René
23 November 2011, 12:24 pmDetermining the majority.
Inform. Process. Lett. 47 (1993), no. 5, 253–255.
saar:
in the first problem, what do the gold medal?
26 November 2011, 2:11 pm(we can take 2 bronze medals and 1 silver against 2 bronze medals and 1 silver
if they equal, the fake is one from 2 medals we did not put, we can find whice in one time
if not, put from the wick side bronze against bronze)
it is too simple, i beleave there is some mistake
Animesh:
@saar It’s not simple, as using ur approach we run into a problem after the first step if 2B + 1S = 2B + 1S, we are left with 1G,1B,1S.
So fake one can be from 3 of them…
if I again do 1B + 1S = 1B (from previous weighting) + 1S (from previous weighting), again I don’t know which one from left hand side is less. If equal of course gold is fake….so no issues….but if left hand side is less than I am stuck…i have done two weightings already!
B = Bronze, S= Silver and G = Gold
27 November 2011, 8:42 amsaar:
thanks
27 November 2011, 2:13 pmu nean that the gold one may be fake, if all the b and s are not. i did not understand so, i hope u are right, and there is solution to this riddle.
Goin2space:
I thought though that the riddle states the fake weighs less than the corresponding real, with this you might be able to assume that there is more than one of the medal that is fake, eliminating the gold. You could then go with saar’s assumption.
2B+1S = 2B+1S
True- weigh one previous B against un-weighed B -if equal then un-weighed silver is fake, else lighter B is fake
False- weigh lighter side B medals against each other-if equal silver from lighter side is fake, else lighter B is fake
again this assumes that the fake has a corresponding medal… which the gold does not.
27 November 2011, 3:37 pmTanya Khovanova:
The gold coin might be fake too.
27 November 2011, 6:50 pmAnimesh:
Yes Gold coin might be fake too 🙂
So in the next weighing instead of
if I again do 1B + 1S = 1B (from previous weighting) + 1S (from previous weighting),
Do 1B + 1S(From previous weighting) = 1S + 1B(From previous weighting)
Since previous weighting (or first weighting) had turned out equal…we are sure all the medals were genuine….
So if any side is lighter I will automatically come to know which one is fake…Bronze or Silver… (this is the second weighting)
And if both are equal…it has to be gold!
So the twist according to me is how you change the equation for next weighting.
27 November 2011, 8:56 pmAnimesh:
I like the second one….but still not sure of the solution….lemme try..
for 3 coins…it’s simple…i should be able to find it in 1 weighting…coz only 1 is fake
so i just take 2 coins..and if unequal…the left over is genuine…
for 4 coins also it’s easy…but for 5 coins it’s different…i should be able to do it in 5-1-1 = 3 weightings only
so i use
1,2 in first weighting
3,4 in second weighting
if both are unequal then of course 5 is the genuine coin coz there can’t be more than 2 fake’s
4 December 2011, 10:55 amif however
1=2, and 3 not equal to 4….
then either both 1 and 2 are genuine or both are fake with same weight…
3 can be G or F…..and same goes for 4….here for the last weighting i compare 3 with 1..if equal then it’s genuine..coz 1=2=3
if 1 3 then 1 & 2 are both genuine….coz if they were both fake and equal then max number of fakes can’t be greater than 2
so 3 would have been equal to 4.
I think the trick has to do with pairs….but am not able to relate it to logic of number of 1’s in binary expansion….
David Reynolds:
Concerning the second problem:
15 July 2013, 5:55 pmBy the problem description, less than half of the coins can be fake. The main goal will be to find and eliminate the fakes. For one and two coins, no fakes. For three coins, there is at most one fake. Weigh coins 1 and 2. If they balance, they must be real. If not, one of them is the fake. Four coins is done the same as three. Five coins begins to get interesting. Weigh coins 1 and 2. If they do not balance, at least one is fake. Put both aside and we are left with three coins with not more than one fake; a case we’ve already covered. This is true in every case that two coins do not balance. Remove both and C coins/W weighings is reduced to C-2 coins/W-1 weighings. If coins 1 and 2 balance, weigh coins 3 and 4. If they balance then all four might be real, or two might be real and two fake. Weigh coins 1 and 3. If they balance, the first four coins are real. If not, then two of them must be fake but we don’t know which. It doesn’t matter as the fifth coin must be real.
Jumping to nine coins.
Weigh 1 and 2. If they do not balance, remove both and case is reduced to seven coins.
Weigh 3 and 4. If they do not balance, remove both and case is reduced to seven coins.
Weigh 1 and 3. If they do not balance, remove all four and case is reduced to five coins.
Assuming all three weighings balanced, weigh 5 and 6, then 7 and 8, then 5 and 7. As before, if any do not balance, we reduce to a case of fewer coins.
If the latter weighings all balance, then all the coins may be real or four may be real and four fake.
Now weigh coins 1 and 5. If they balance, all the coins are real. If not, four are fake so coin 9 must be real.
So in general, we always create groups of coins, equal in number that weigh the same, then compare them against each other.
Anytime they do not balance, we remove them all since at least half must be fake, always preserving the fact that the remaining group is comprised of mostly real coins.